package com.vint.lintcode;

import com.vint.common.ListNode;

/**
 * 判断是否回文链表， 1->2->1
 */
public class Lintcode223 {
	public boolean isPalindrome(ListNode head) {

		if (null == head) {
			return true;
		}
		ListNode oldHead = head;
		ListNode nHead = copySelf(oldHead);
		ListNode newHead = reverse(nHead);
		while (null != head) {
			if (head.val != newHead.val){
				return false;
			}
			head = head.next;
			newHead = newHead.next;
		}
		return true;
	}

	public ListNode copySelf(ListNode head) {
		if (null == head) {
			return null;
		}
		ListNode visit = new ListNode(head.val);
		ListNode newHead = visit;
		ListNode newVisit = head.next;
		while (null != newVisit) {
			visit.next = new ListNode(newVisit.val);
			visit = visit.next;
			newVisit = newVisit.next;
		}
		return newHead;
	}
	public ListNode reverse(ListNode head) {
		if (null == head || null == head.next) {
			return head;
		}
		ListNode newHead = head;
		ListNode walk = head.next;
		newHead.next = null;
		while (null != walk) {
			ListNode nextWalk = walk.next;
			walk.next = newHead;
			newHead = walk;
			walk = nextWalk;
		}
		return newHead;
	}
}

